Role Mining in the Presence of Noise.

UICDS compliant resource management system for emergency response.

Automating Security Configuration and Administration An Access Control Perspective.

Ensuring Privacy and Security for LBS through Trajectory Partitioning.

Privacy%2Dpreserving trust verification.

The role mining problem A formal perspective.

Anonymization models for directional location based service environments.

Spatial neighborhood based anomaly detection in sensor datasets.

Efficient privacy%2Dpreserving similar document detection.

Data and Applications Security XXIII

A Secure Revised Simplex Algorithm for Privacy%2DPreserving Linear Programming.

Effective anonymization of query logs.

An efficient online auditing approach to limit private data disclosure.

Extended Boolean Matrix Decomposition.

Efficient Privacy%2DPreserving Link Discovery.
Abstract. Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealed from link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph. We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance. We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.
Efficient Privacy%2DPreserving Link Discovery.
Abstract. Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealed from link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph. We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance. We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.
An Efficient Approximate Protocol for Privacy%2DPreserving Association Rule Mining.

Privacy%2Dpreserving linear programming.

Preserving Privacy in Social Networks A Structure%2DAware Approach.

Secure Multiparty Computation Methods.
We introduce a novel approach to general secure multiparty computation that avoids the intensive use of verifiable secret sharing characterizing nearly all previous protocols in the literature. Instead, our scheme involves manipulation of ciphertexts for which the underlying private key is shared by participants in the computation. The benefits of this protocol include a high degree of conceptual and structural simplicity, low message complexity, and substantial flexibility with respect to input and output value formats. We refer to this new approach as mix and match. While the atomic operations in mix and match are logical operations, rather than full field operations as in previous approaches, the techniques we introduce are nonetheless highly practical for computations involving intensive bitwise manipulation. One application for which mix and match is particularly well suited is that of sealed-bid auctions. Thus, as another contribution in this paper, we present a practical, mix-and-match-based auction protocol that is fully private and non-interactive and may be readily adapted to a wide range of auction strategies.
Vertically Partitioned Data.
ii iii ACKNOWLEDGMENTS I would like to acknowledge the overwhelming contribution and endless hours invested in me (“the biggest time sink”) by my advisor, Prof. Chris Clifton. Without him, I would not even be close to being done. Apart from all his advisory help, I also have to thank this self proclaimed “information junkie”, for all the useful trivia I have harvested over the past couple of years from him. I would also like to acknowledge the innumerable contributions of my prior advisor and current committee member, Prof. Mike Atallah. Without his constant support and confidence in my abilities, I could not have continued in the Ph.D. program. Prof. Sonia Fahmy also helped me out when the going seemed tough and I was floundering in the search of a new research direction. Thank you. I would also like to thank my committee members for their careful reading of the dissertation and useful comments. For me, the heart and soul of the Computer Science Department at Purdue has
Privacy%2DPreserving Kth Element Score over Vertically Partitioned Data.

Edge%2DRMP Minimizing administrative assignments for role%2Dbased access control.

Privacy%2Dpreserving indexing of documents on the network.
We address the problem of providing privacypreserving  search over distributed accesscontrolled  content. Indexed documents can  be easily reconstructed from conventional (inverted)  indexes used in search. The need to  avoid breaches of access-control through the  index requires the index hosting site to be  fully secured and trusted by by all participating  content providers. This level of trust is  impractical in the increasingly common case  where multiple competing organizations or individuals  wish to selectively share content. We  propose a solution that eliminates the need of  such a trusted authority. The solution builds  a centralized privacy-preserving index in conjunction  with a distributed access-control enforcing   search protocol. The new index provides  strong and quantifiable privacy guarantees  that hold even if the entire index is made  public. Experiments on a real-life dataset validate  performance of the scheme. The appeal  of our solution is two-fold: (a) Content  providers maintain complete control in defining  access groups and ensuring its compliance,  and (b) System implementors retain tunable  knobs to balance privacy and e#ciency concerns  for their particular domains.
The Role Hierarchy Mining Problem Discovery of Optimal Role Hierarchies.

Secure Construction of Contingency Tables from Distributed Data.

Secure information sharing and analysis for effective emergency management.

Optimal Boolean Matrix Decomposition Application to Role Engineering.
Abstract — A decomposition of a binary matrix into two matrices gives a set of basis vectors and their appropriate combination to form the original matrix. Such decomposition solutions are useful in a number of application domains including text mining, role engineering as well as knowledge discovery. While a binary matrix can be decomposed in several ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions optimizing different criteria matching various semantics. In this paper, we first present a number of variants to the optimal Boolean matrix decomposition problem that have pragmatic implications. We then present a unified framework for modeling the optimal binary matrix decomposition and its variants using binary integer programming. Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for binary integer programming. Although the proposed solutions are applicable to any domain of interest, for providing more meaningful discussions and results, in this paper, we present the binary matrix decomposition problem in a role engineering context, whose goal is to discover an optimal and correct set of roles from existing permissions, referred to as the role mining problem (RMP). This problem has gained significant interest in recent years as role based access control has become a popular means of enforcing security in databases. We consider several variants of the above basic RMP, including the min-noise RMP, δ-approximate RMP and edge-RMP. Solutions to each of them aid security administrators in specific scenarios. We then model these variants as Boolean matrix decomposition and present efficient heuristics to solve them. I.
A Profile Anonymization Model for Privacy in a Personalized Location Based Service Environment.

Privacy%2Dpreserving link discovery.
Abstract. Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealed from link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph. We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance. We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.
Migrating to optimal RBAC with minimal perturbation.

Efficient security policy enforcement for the mobile environment.
  Recent enhancements in location technologies reliability and precision are fostering the development of a new wave of applications that make use of the location information of users. Such applications introduces new aspects of access control which should be addressed. On the one side, precise location information may play an important role and can be used to develop Location-based Access Control (LBAC) systems that integrate traditional access control mechanisms with conditions based on the physical position of users. On the other side, location information of users can be considered sensitive and access control solutions should be developed to protect it against unauthorized accesses and disclosures. In this chapter, we address these two aspects related to the use and protection of location information, discussing existing solutions, open issues, and some research directions. 
Privacy%2Dpreserving SVM classification.
Traditional Data Mining and Knowledge Discovery algorithms assume free access to data, either at a centralized location or in federated form. Increasingly, privacy and security concerns restrict this access, thus derailing data mining projects. What is required is distributed knowledge discovery that is sensitive to this problem. The key is to obtain valid results, while providing guarantees on the non-disclosure of data. Support vector machine classification is one of the most widely used classification methodologies in data mining and machine learning. It is based on solid theoretical foundations and has wide practical application. This paper proposes a privacy-preserving solution for support vector machine (SVM) classification, PP-SVM for short. Our solution constructs the global SVM classification model from the data distributed at multiple parties, without disclosing the data of each party to others. We assume that data is horizontally partitioned – each party
An Approach to Securely Identifying Beneficial Collaboration in Decentralized Logistics Systems.
doi 10.1287/msom.1070.0167
Privacy%2Dpreserving decision trees over vertically partitioned data.
Abstract. Privacy and security concerns can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. In this paper, we tackle the problem of classification. We introduce a generalized privacy preserving variant of the ID3 algorithm for vertically partitioned data distributed over two or more parties. Along with the algorithm, we give a complete proof of security that gives a tight bound on the information revealed. 1
Privacy%2Dpreserving Na%EFve Bayes classification.

Enabling Better Medical Image Classification Through Secure Collaboration.
Privacy is of growing concern in today’s day and age. Protecting the privacy of health data is of paramount importance. With the rapid advancement in imaging technology, analysis of medical images is now one of the most dynamic fields of study today. Image analysis is performed for a variety of purposes, ranging from image enhancement to image segmentation. It can easily be seen that having access to more information makes the analysis results more accurate. For example, supervised classification based image segmentation requires good and plentiful training data. We wish to utilize the training data at different locations to obtain more accurate image segmentation while still protecting the privacy of individual patients. Work in the field of secure multi-party computation (SMC) in cryptography shows how to compute functions securely and quantifies what it means to be secure. Applying SMC protocols in image processing is a challenging problem. This paper looks at how some of this work can be leveraged to perform privacy-preserving image analysis and classification.
The role mining problem finding a minimal descriptive set of roles.
Devising a complete and correct set of roles has been recognized as one of the most important and challenging tasks in implementing role based access control. A key problem related to this is the notion of goodness/interestingness – when is a role good/interesting? In this paper, we define the role mining problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions. The main contribution of this paper is to formally define RMP, and analyze its theoretical bounds. In addition to the above basic RMP, we introduce two different variations of the RMP, called the δ-approx RMP and the Minimal Noise RMP that have pragmatic implications. We reduce the known “set basis problem ” to RMP to show that RMP is an NP-complete problem. An important contribution of this paper is also to show the relation of the role mining problem to several problems already identified in the data mining and data analysis literature. By showing that the RMP is in essence reducible to these known problems, we can directly borrow the existing implementation solutions and guide further research in this direction.
Using semantics for automatic enforcement of access control policies among dynamic coalitions.

RoleMiner mining roles using subset enumeration.
Role engineering, the task of defining roles and associating permissions to them, is essential to realize the full benefits of the role-based access control paradigm. Essentially, there are two basic approaches to accomplish this: the topdown and the bottom-up. The top-down approach relies on a careful analysis of the business processes to define job functions and then specify appropriate roles from them. While this approach can aid in defining roles more accurately, it is tedious and time consuming since it requires that the semantics of the business processes be well understood. Moreover, it ignores existing permissions within an organization and does not utilize them. On the other hand, the bottomup approach starts with existing permissions and attempts to derive roles from them, thus helping to automate role definition. In this paper, we present an unsupervised approach called RoleMiner that mines roles from existing userpermission assignments. Since a role is nothing but a set of permissions, when no semantics are available, the task of role mining is essentially that of clustering users that have same (or similar) permissions. However, unlike the traditional applications of data mining that ideally require identification of non-overlapping clusters, roles will have overlapping permission needs and thus permission sets that define roles should be allowed to overlap. It is this distinction from traditional clustering that makes the problem of role mining non-trivial. Our experiments with real and simulated data sets indicate that our role mining process is quite accurate and efficient.
Privacy%2DPreserving SVM Classification on Vertically Partitioned Data.

Privacy%2Dpreserving SVM using nonlinear kernels on horizontally partitioned data.
Traditional Data Mining and Knowledge Discovery algorithms assume free access to data, either at a centralized location or in federated form. Increasingly, privacy and security concerns restrict this access, thus derailing data mining projects. What is required is distributed knowledge discovery that is sensitive to this problem. The key is to obtain valid results, while providing guarantees on the non-disclosure of data. Support vector machine classification is one of the most widely used classification methodologies in data mining and machine learning. It is based on solid theoretical foundations and has wide practical application. This paper proposes a privacy-preserving solution for support vector machine (SVM) classification, PP-SVM for short. Our solution constructs the global SVM classification model from the data distributed at multiple parties, without disclosing the data of each party to others. We assume that data is horizontally partitioned – each party
Privacy%2DPreserving Decision Trees over Vertically Partitioned Data.
Abstract. Privacy and security concerns can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. In this paper, we tackle the problem of classification. We introduce a generalized privacy preserving variant of the ID3 algorithm for vertically partitioned data distributed over two or more parties. Along with the algorithm, we give a complete proof of security that gives a tight bound on the information revealed. 1
Knowledge Discovery from Transportation Network Data.
Transportation and Logistics are a major sector of the economy, however data analysis in this domain has remained largely in the province of optimization. The potential of data mining and knowledge discovery techniques is largely untapped. Transportation networks are naturally represented as graphs. This paper explores the problems in mining of transportation network graphs: We hope to find how current techniques both succeed and fail on this problem, and from the failures, we hope to present new challenges for data mining. Experimental results from applying both existing graph mining and conventional data mining techniques to real transportation network data are provided, including new approaches to making these techniques applicable to the problems. Reasons why these techniques are not appropriate are discussed. We also suggest several challenging problems to precipitate research and galvanize future work in this area. 1
Privacy%2DPreserving Top%2DK Queries.
There is an increasing need for ranked and “best match” queries, in particular the top-k query: Finding the k closest matches to a query “point”. Top-k queries are particularly relevant when dealing with privacy-sensitive information. For example, profiling has potential anti-terrorism applications (e.g., finding visa applicants who are likely terrorists). Profiles rarely match individuals exactly- a prime example of the need for similarity or best match queries. However, profiles often match innocent people (or transactions), subjecting them to unwarranted scrutiny. By stripping a top-k query to its minimum – disclosing only an unranked set of k matches – we meet the goals of the top-k query while maintaining the privacy concept of k-anonymity[5]. In the context of profiling, k-anonymity requires that any individual that “matches ” be indistinguishable
Collusion Set Detection Through Outlier Discovery.

Secure set intersection cardinality with application to association rule mining.
There has been concern over the apparent conflict between privacy and data mining. There is no inherent conflict, as most types of data mining produce summary results that do not reveal information about individuals. The process of data mining may use private data, leading to the potential for privacy breaches. Secure Multiparty Computation shows that results can be produced without revealing the data used to generate them. The problem is that general techniques for secure multiparty computation do not scale to data-mining size computations. This paper presents an efficient protocol for securely determining the size of set intersection, and shows how this can be used to generate association rules where multiple parties have different (and private) information about the same set of individuals. 1
Privacy%2Dpreserving data integration and sharing.
The goal of this paper is to identify potential research directions and challenges that need to be addressed to perform privacy preserving data integration. Increasing privacy and security consciousness has lead to increased research (and development) of methods that compute useful information in a secure fashion. Data integration and sharing have been a long standing challenge for the database community. This need has become critical in numerous contexts, including integrating data on the Web and at enterprises, building ecommerce market places, sharing data for scientific research, data exchange at government agencies, monitoring health crises, and improving homeland security. Unfortunately, data integration and sharing are hampered by legitimate and widespread privacy concerns. Companies could exchange information to boost productivity, but are prevented by fear of being exploited by competitors or antitrust concerns. Sharing healthcare data could improve scientific research, but the cost of obtaining consent to use individually identifiable information can be prohibitive. Sharing healthcare and consumer data enables early detection of disease outbreak[16], but without provable privacy protection it is difficult to extend these surveillance measures nationally or internationally. Fire departments could
Privacy%2DPreserving Outlier Detection.
Outlier detection can lead to the discovery of truly unexpected knowledge in many areas such as electronic commerce, credit card fraud and especially national security. We look at the problem of finding outliers in large distributed databases where privacy/security concerns restrict the sharing of data. Both homogeneous and heterogeneous distribution of data is considered. We propose techniques to detect outliers in such scenarios while giving formal guarantees on the amount of information disclosed. 1.
Privacy%2DPreserving Data Mining Why%2C How%2C and When.

Privacy Preserving Na%EFve Bayes Classifier for Vertically Partitioned Data.

Privacy%2DPreserving Data Mining Why%2C How%2C and When.

Privacy%2Dpreserving k%2Dmeans clustering over vertically partitioned data.
 
Leveraging the %22Multi%22 in secure multi%2Dparty computation.
Secure Multi-Party Computation enables parties with private data to collaboratively compute a global function of their private data, without revealing that data. The increase in sensitive data on networked computers, along with improved ability to integrate and utilize that data, make the time ripe for practical secure multi-party computation. This paper surveys approaches to secure multi-party computation, and gives a method whereby an e#cient protocol for two parties using an untrusted third party can be used to construct an e#cient peer-to-peer secure multi-party protocol.
Privacy preserving association rule mining in vertically partitioned data.
Privacy considerations often constrain data mining projects. This paper addresses the problem of association rule mining where transactions are distributed across sources. Each site holds some attributes of each transaction, and the sites wish to collaborate to identify globally valid association rules. However, the sites must not reveal individual transaction data. We present a two-party algorithm for efficiently discovering frequent itemsets with minimum support levels, without either site revealing individual transaction values.
Tools for Privacy Preserving Data Mining.
We provide here an overview of the new and rapidly emerging research area of privacy preserving data mining. We also propose a classification hierarchy that sets the basis for analyzing the work which has been performed in this context. A detailed review of the work accomplished in this area is also given, along with the coordinates of each work to the classification hierarchy. A brief evaluation is performed, and some initial conclusions are made.
